package com.xinwei.leetcode.数组;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

// https://leetcode-cn.com/problems/find-all-numbers-disappeared-in-an-array/
public class _448_找到所有数组中消失的数字 {
    // 最普通的：用HashSet来储存出现过的数字
    public List<Integer> findDisappearedNumbers(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            set.add(nums[i]);
        }
        ArrayList<Integer> list = new ArrayList<>(nums.length);
        for (int i = 1; i <= nums.length; i++) {
            if (!set.contains(i)) {
                list.add(i);
            }
        }
        return list;
    }

    // 原地修改 优化：把空间复杂度优化到O（1）
    // 先遍历一遍数组int num : nums，把nums[num]上的数字加n，最后遍历数组，小于n的位置就是没出现过的num
    // 因为有可能一个位置重复加n，所以要取模
    public List<Integer> findDisappearedNumbers1(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            int x = (nums[i] - 1) % n;
            nums[x] += n;
        }
        ArrayList<Integer> list = new ArrayList<>(nums.length);
        for (int i = 0; i < n; i++) {
            if (nums[i] <= n) {
                list.add(i + 1);
            }
        }
        return list;
    }
}
